#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>
#include <set>
#include <string>

/*! \author Guillaume Collombet - Rachid Delory*/
/*! \date 25/11/2012 */
/*! \mainpage LIF15 Génération d'automate non déterministe avec ou sans epsilone transition
 * \subsection Introduction
 * L'objectif de ce TP est de réaliser un programme qui prend en entrée un mot et qui détermine si ce mot est reconnu par un automate à états finis non déterministe dont la description est lue dans un fichier. Un second programme est demandé, c'est l'extension du premier aux automates avec transitions spontanées.
 * \subsection running Executer le programme
 * En ligne de commande. le fichier ndet permet d'executer des automates déterministes et ndetepsilon des automates non déterministes.
 * Ils accepte optionelement en entrée le chemin d'un fichier décrivant un automate.
 */

using namespace std;

const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;

typedef size_t                            etat_t;
typedef unsigned char                     symb_t;
typedef set< etat_t >                     etatset_t;
typedef vector< vector< etatset_t > >     trans_t;

/*!
 * \brief Répresente un automate finit non deterministe sans epsilon transition
 */
struct sAutoND{
    // caractéristiques
    size_t nb_etats;
    size_t nb_symbs;
    size_t nb_finaux;

    etat_t initial;
    // état initial

    etatset_t finaux;
    // états finaux : etatset_t peut être un int*, un tableau dynamique comme vector<int>
    // ou une autre structure de donnée de votre choix.

    trans_t trans;
    // matrice de transition : trans_t peut être un int***, une structure dynamique 3D comme vector< vector< set<int> > >
    // ou une autre structure de donnée de votre choix.
};

/*!
 * \brief FromFile lit le fichier en entré et remplit la structure automate avec les informations luent.
 * \param at automate à renseigner
 * \param path chemin du fichier contenant la description de l'automate
 * \return TRUE si la lecture s'est bien passée, FALSE sinon
 */
bool FromFile(sAutoND& at, string path){
    ifstream myfile(path.c_str(), ios::in);
    //un flux d'entree obtenu à partir du nom du fichier
    string line;
    // un ligne lue dans le fichier avec getline(myfile,line);
    istringstream iss;
    // flux associé à la chaine, pour lire morceau par morceau avec >> (comme cin)
    etat_t s(0), t(0);
    // deux états temporaires
    symb_t a(0);
    // un symbole temporaire

    if (myfile.is_open()){
        // la première ligne donne 'nb_etats nb_symbs nb_finaux'
        do{
            getline(myfile,line);
        } while (line.empty() || line[0]=='#');
        // on autorise les lignes de commentaires : celles qui commencent par '#'
        iss.str(line);
        if((iss >> at.nb_etats).fail() || (iss >> at.nb_symbs).fail() || (iss >> at.nb_finaux).fail())
            return false;
        // la deuxième ligne donne l'état initial
        do{
            getline (myfile,line);
        } while (line.empty() || line[0]=='#');
        iss.clear();
        iss.str(line);
        if((iss >> at.initial).fail())
            return -1;

        // les autres lignes donnent les états finaux
        for(size_t i = 0; i < at.nb_finaux; i++){
            do{
                getline (myfile,line);
            } while (line.empty() || line[0]=='#');
            iss.clear();
            iss.str(line);
            if((iss >> s).fail())
                continue;
            at.finaux.insert(s); //remplir finaux
            cerr << "s= " << s << endl;
        }

        // on alloue les vectors à la taille connue à l'avance pour éviter les resize dynamiques
        at.trans.resize(at.nb_symbs);
        for(size_t i=0;i<at.nb_symbs;++i)
            at.trans[i].resize(at.nb_etats);

        // lecture de la relation de transition
        while(myfile.good()){
            line.clear();
            getline (myfile,line);
            if (line.empty() && line[0]=='#')
                continue;
            iss.clear();
            iss.str(line);

            // si une des trois lecbooltures echoue, on passe à la suite
            if((iss >> s).fail() || (iss >> a).fail() || (iss >> t).fail() || (a< ASCII_A ) || (a> ASCII_Z ))
                continue;

            cerr << "s=" << s<< ", a=" << a-ASCII_A << ", t=" << t << endl;
            at.trans[a - 97][s].insert(t); //remplit trans

        }
        myfile.close();
        return true;
    }
    return false;
    // on ne peut pas ouvrir le fichier
}

/*!
 * \brief EstDeterministe Test si l'automate passé en argument est déterministe.
 * \param at automate
 * \return VRAI si l'automate est déterministe, FALSE sinon
 */
bool ContientFinal(const sAutoND& at,const etatset_t& e){
    // Cette fonction prend un automate et un ensemble d'état et indique si cet ensemble
    // contient au moins un etat final

    set<etat_t>::const_iterator first1 = at.finaux.begin();
    set<etat_t>::const_iterator last1 = at.finaux.end();
    set<etat_t>::const_iterator first2 = e.begin();
    set<etat_t>::const_iterator last2 = e.end();

    while ((first1!=last1) && (first2!=last2))
    {
        if (*first1<*first2)
            first1++;
        else{
            if (*first2<*first1)
                first2++;
            else
                return true;
        }
    }
    return false;
}

/*!
 * \brief EstDeterministe Test si l'automate passé en argument est déterministe.
 * \param at automate
 * \return VRAI si l'automate est déterministe, FALSE sinon
 */
bool EstDeterministe(const sAutoND& at){
    // Cette fonction prend un automate et indique s'il est déterministe ou pas
    for (trans_t::const_iterator i = at.trans.begin(); i != at.trans.end(); i++)
    {
        for (vector<etatset_t>::const_iterator j = (*i).begin(); j != (*i).end(); j++)
        {
            if((*j).size() > 1)
                return false;
        }
    }
    return true;
}

/*!
 * \brief Delta Cette fonction prend un automate, un ensemble d'état E={e_0, e_1, ... ,e_n}
     et renvoie l'ensemble des états accessibles depuis au moins un des e_i.
     Autrement dit, c'est l'union des ensembles d'états x_i tels que x_i = {x | (e_i,c,x) in Delta}
 * \param at automate
 * \param e ensemble d'états
 * \param c symbole à lire par l'automate de type unsigned char
 * \return
 */
etatset_t Delta(const sAutoND& at, const etatset_t& e, symb_t c){
    // Cette fonction prend un automate, un ensemble d'état E={e_0, e_1, ... ,e_n}
    // et renvoie l'ensemble des états accessibles depuis au moins un des e_i.
    // Autrement dit, c'est l'union des ensembles d'états x_i tels que x_i = {x | (e_i,c,x) in Delta}
    etatset_t res;
    for (etatset_t::const_iterator i = e.begin(); i != e.end(); i++)
    {
        for (etatset_t::const_iterator j = at.trans[c-97][(*i)].begin(); j != at.trans[c-97][(*i)].end(); j++)
        {
            res.insert(*j);
        }
    }
    return res;
}

/*!
 * \brief Accept Cette fonction prend en argument un automate et détermine si il accepte le mot str
 * \param at automate
 * \param str chaine de caractère de type string à lire par l'automate
 * \return VRAI si la chaine de caractère passé en argument est acceptée par l'automate, FAUX sinon
 */
bool Accept(const sAutoND& at, string str){
    // Cette fonction prend un automate et détermine si il accepte le mot str
    // On utilesera bien sûr la fonction Delta.

    //TODO définir cette fonction
    etatset_t res;
    res.insert(at.initial);
    for(string::const_iterator it = str.begin(); it != str.end(); it++)
    {
        res = Delta(at, res, *it);
    }
    if(ContientFinal(at,res))
        return true;
    return false;
}


/*!
 * \brief main Fonction principale
 */
int main(int argc, char* argv[]){
    string path, str;
    bool r;
    sAutoND at;

    cout << "***TP LIF 15 ***" << endl;

    if(argc > 1)
        path.assign(argv[1]);
    else
        path = "./exempleND.txt";

    if(argc > 2)
        str.assign(argv[2]);
    else
        str = "abb";

    if (!FromFile(at, path)){
        cerr << "Erreur de lecture du fichier " << path << endl;
    }else{
        cerr << "Automate déterministe ? " << (EstDeterministe(at) ? "Vrai" : "Faux") << endl;
        r = Accept(at, str);
        cout << "'" << str  <<  "' est accepté ? " << (r ? "Vrai" : "Faux") << endl;
    }
    
    return EXIT_SUCCESS;
}
